package day6;

public class 链表相加 {
	//链表逆置
	public ListNode reverse(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur=reverse(head.next);
        ListNode node=head.next;
        node.next=head;
        head.next=null;
        return cur;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        head1=reverse(head1);
        head2=reverse(head2);
        //添加虚拟头结点
        ListNode head=new ListNode(0);
        ListNode p=head;
        int tmp=0;
        //模拟加法，逻辑见模版说明
        while(head1!=null||head2!=null||tmp!=0){
            if(head1!=null){
                tmp+=head1.val;
                head1=head1.next;
            }
            if(head2!=null){
                tmp+=head2.val;
                head2=head2.next;
            }
            //注意不能再循环内新建节点，因为临时变量出作用域销毁；
            p.next=new ListNode(tmp%10);
            p=p.next;
            tmp/=10;
        }
        return reverse(head.next);
    }
}
